相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4785
出题人传送门:http://jiruyi910387714.is-programmer.com/posts/209073.html
官方题解:https://pan.baidu.com/s/1dFGHFfr
解题报告
我们发现正常的代码是统计的前缀和
但劼的写法实际是统计后缀和
然后画一画发现,只有$l-1,r$这两个点被改到的时候才会影响答案
我们考虑询问区间是$[l,r]$,一个修改区间是$[a,b]$
那么如果$l,r \in [a,b]$则这个修改区间有$\frac{2}{b-a+1}$的可能影响到答案
如果$l,r$只有一个$\in [a,b]$那么这个修改区间有$\frac{1}{b-a+1}$的可能影响到答案
如果两个都不属于,其显然不会影响到答案
于是我们把修改操作看成二维平面上的点的话
每一个询问操作可以拆成三个矩阵的询问
这个是经典问题,可以用树套树/分治/K-d Tree来解决
至于怎么维护标记,直接做的话,我们可以看成矩阵乘法
因为这个转移矩阵非常特殊,搞一搞发现其不但满足结合律,还满足交换律,所以可以标记永久化
但还有更妙的做法:
我们可以搞一个类似生成函数的东西
设第$i$个操作有$p_i$的可能影响到当前询问,设两个端点被改变偶数次的概率为$a$,奇数次为$b$
那么最后$a-b=\prod\limits_{i}{(1-p_i)-p_i}$
为什么是对的呢?因为只有改变奇数次才会为奇数,而$-1$的奇数次方等于$-1$偶数次方等于$1$,所以刚好对上
又因为我们还知道$a+b=1$,所以$a = \frac{1+\prod\limits_{i}{(1-p_i)-p_i}}{2}$
另外的话,这题有一个坑点:如果$l-1=0$的话,我们需要特判
因为之前我们的推导基于$l-1$那个点记录的是一个后缀
而实际算法中我们我们默认$l-1$那个点的值为$0$,所以需要判断一下总操作次数奇偶
考试的时候就这一点没想到,血wa三小时,最后这题挂零
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int M = 30000000; const int MOD = 998244353; const int REV = 499122177; inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int n,m,tot; class Segment_Tree{ int cnt,root,AnsTmp,ch[M][2],prod[M][2]; public: inline void modify(int x, int y, int v, bool t) { modify(root, 1, n, x, y, v, t); } inline int query(int x1, int x2, int y1, int y2, bool t) { if (x1 > x2 || y1 > y2) return 1; AnsTmp = 1; query(root, 1, n, x1, x2, y1, y2, t); return (AnsTmp+MOD)%MOD; } private: void modify(int &w, int l, int r, int x, int y, int v, bool t) { //X if (!w) w = ++cnt; modify(prod[w][0], 1, n, y, v, t); if (l < r) { int mid = l + r + 1 >> 1; if (x < mid) modify(ch[w][0], l, mid-1, x, y, v, t); else modify(ch[w][1], mid, r, x, y, v, t); } } void modify(int &w, int l, int r, int p, int v, bool t) { //Y if (!w) w = ++cnt, prod[w][0] = prod[w][1] = 1; prod[w][t] = (LL)prod[w][t] * v % MOD; if (l < r) { int mid = l + r + 1 >> 1; if (p < mid) modify(ch[w][0], l, mid-1, p, v, t); else modify(ch[w][1], mid, r, p, v, t); } } void query(int w, int l, int r, int L, int R, int y1, int y2, bool t) { //X if (!w) return; if (L <= l && r <= R) query(prod[w][0], 1, n, y1, y2, t); else { int mid = l + r + 1 >> 1; if (L < mid) query(ch[w][0], l, mid-1, L, R, y1, y2, t); if (mid <= R) query(ch[w][1], mid, r, L, R, y1, y2, t); } } void query(int w, int l, int r, int L, int R, bool t) { //Y if (!w) return; if (L <= l && r <= R) AnsTmp = (LL)AnsTmp * prod[w][t] % MOD; else { int mid = l + r + 1 >> 1; if (L < mid) query(ch[w][0], l, mid-1, L, R, t); if (mid <= R) query(ch[w][1], mid, r, L, R, t); } } }SGT; inline int Pow(int w, int t) { int ret = 1; for (;t;t>>=1,w=(LL)w*w%MOD) if (t&1) ret=(LL)ret*w%MOD; return ret; } int main() { n = read(); m = read(); for (int i=1,l,r,len,ret;i<=m;i++) { if (read() == 1) { l = read(); r = read(); len = Pow(r-l+1, MOD-2); ++tot; SGT.modify(l, r, (1 - (len * 2ll)) % MOD, 0); SGT.modify(l, r, (1 - (len * 4ll)) % MOD, 1); } else { l = read() - 1; r = read(); ret = 1; ret = (LL)ret * SGT.query(1, l, l, r - 1, 0) % MOD; ret = (LL)ret * SGT.query(l+1, r, r, n, 0) % MOD; ret = (LL)ret * SGT.query(1, l, r, n, 1) % MOD; ret = (ret + 1ll) * REV % MOD; if (!l&&(tot&1)) ret = (1 - ret) % MOD; printf("%d\n",(ret+MOD)%MOD); } } return 0; }
Woah! I’m really digging the template/theme of this website.
It’s simple, yet effective. A lot of times it’s very hard to get that “perfect balance” between superb usability and visual appearance.
I must say that you’ve done a excellent job with this.
In addition, the blog loads super quick for me on Firefox.
Superb Blog!
I am genuinely grateful to the holder of this web site who has
shared this wonderful paragraph at here.
Nice blog here! Also your web site loads up very fast!
What web host are you using? Can I get your affiliate link to your host?
I wish my website loaded up as quickly as
yours lol
Hmm is anyone else encountering problems with the pictures
on this blog loading? I’m trying to determine if its a problem
on my end or if it’s the blog. Any feedback would be
greatly appreciated.
What’s up, I check your new stuff regularly. Your humoristic style is awesome, keep it up!
Nice blog! Is your theme custom made or did you download it from somewhere?
A design like yours with a few simple tweeks would really make my
blog stand out. Please let me know where you got your design.
Many thanks
I am sure this piece of writing has touched all the internet users,
its really really nice article on building up
new webpage.
Hi, Neat post. There’s a problem along with your web site in internet explorer,
may check this? IE nonetheless is the market leader and a large
component to other people will leave out your magnificent writing due to this
problem.
Greetings! Very useful advice in this particular article!
It is the little changes that will make the largest changes.
Thanks a lot for sharing!
Wow, marvelous blog layout! How long have you been blogging for?
you made blogging look easy. The overall look of your
site is great, as well as the content!
Hello, i think that i saw you visited my website thus i
came to “return the favor”.I am attempting to find things to enhance
my site!I suppose its ok to use a few of your ideas!!
Greate post. Keep writing such kind of information on your blog.
Im really impressed by your site.
Hey there, You have performed an incredible job.
I’ll certainly digg it and in my opinion recommend to my
friends. I’m confident they’ll be benefited from this web site.
Greetings, There’s no doubt that your blog could possibly be having web browser compatibility issues.
Whenever I take a look at your site in Safari, it
looks fine however, when opening in IE, it’s got some overlapping issues.
I merely wanted to provide you with a quick heads up! Besides that,
fantastic blog!
We are a group of volunteers and starting a new scheme in our community.
Your website provided us with valuable information to
work on. You have done an impressive job and our entire community will be grateful to you.
What i don’t understood is in reality how you’re no
longer really much more neatly-preferred than you may
be right now. You are very intelligent. You recognize thus
significantly when it comes to this topic, made me for my part imagine it
from a lot of various angles. Its like women and men aren’t interested except it’s
something to accomplish with Girl gaga! Your individual stuffs outstanding.
Always take care of it up!
Do you have a spam issue on this website; I also am a blogger, and
I was wanting to know your situation; many of us have developed some
nice procedures and we are looking to swap techniques with other
folks, please shoot me an email if interested.
This is my first time go to see at here and i am actually pleassant to read everthing at single place.
Hey there would you mind letting me know which hosting company you’re
utilizing? I’ve loaded your blog in 3 completely different browsers and
I must say this blog loads a lot faster then most.
Can you suggest a good hosting provider at a honest price?
Thanks, I appreciate it!
Hello, i read your blog occasionally and i own a
similar one and i was just curious if you get a lot of spam comments?
If so how do you protect against it, any plugin or anything you can recommend?
I get so much lately it’s driving me crazy so any help is very
much appreciated.
If you desire to take a great deal from this article then you have to apply these techniques to your won blog.
This post offers clear idea designed for the new visitors of blogging, that genuinely
how to do blogging and site-building.
Very quickly this website will be famous amid all blogging and site-building visitors, due to it’s nice articles
or reviews
I have read so many articles about the blogger lovers however this article is truly a pleasant article, keep it up.
pof natalielise
Very good post! We will be linking to this great post on our website.
Keep up the great writing.
It’s very easy to find out any matter on web as compared to books, as I found this
paragraph at this website.
Great blog here! Also your web site loads up very fast!
What web host are you using? Can I get your affiliate link to your
host? I wish my site loaded up as fast as yours lol
My relatives every time say that I am wasting my time here at net,
however I know I am getting familiarity all the time by reading thes pleasant posts.
Hi there, i read your blog occasionally and i own a similar one and i was just wondering if you get a
lot of spam feedback? If so how do you prevent it,
any plugin or anything you can recommend? I get so much lately it’s driving
me crazy so any assistance is very much appreciated.
Have you ever thought about adding a little bit more than just your articles?
I mean, what you say is fundamental and all. Nevertheless think of
if you added some great graphics or videos to give your posts more, “pop”!
Your content is excellent but with pics and videos, this site could undeniably be
one of the most beneficial in its field. Excellent blog!
Thank you for the good writeup. It in fact was a amusement
account it. Look advanced to more added agreeable from you!
However, how could we communicate? natalielise
pof
Thank you for some other magnificent article. The place else could anybody get
that kind of information in such an ideal manner of writing?
I’ve a presentation next week, and I’m at the search for such info.
Today, I went to the beach front with my kids. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put
the shell to her ear and screamed. There was a hermit crab
inside and it pinched her ear. She never wants to go back!
LoL I know this is totally off topic but I had to tell someone!
Definitely believe that which you stated. Your favorite reason seemed to be on the web the easiest thing to be aware of.
I say to you, I certainly get irked while people think about worries that they just do not know
about. You managed to hit the nail upon the top and also defined out the
whole thing without having side effect , people could take a signal.
Will probably be back to get more. Thanks
Awesome article.
An intriguing discussion is worth comment. I believe that you need to publish more about
this subject matter, it might not be a taboo subject
but generally people don’t talk about these subjects.
To the next! All the best!!
When some one searches for his vital thing, so he/she needs to be available that in detail, thus that thing
is maintained over here.
What’s up to all, how is the whole thing, I think every one is getting more
from this website, and your views are fastidious in support of
new users.
Undeniably believe that which you stated. Your favorite reason seemed to
be on the web the simplest thing to be aware of. I say to you, I definitely get irked while people consider
worries that they plainly do not know about.
You managed to hit the nail upon the top as well as
defined out the whole thing without having side-effects , people
can take a signal. Will probably be back to get more.
Thanks
Its like you read my mind! You appear to know so much about this, like you wrote the
book in it or something. I think that you could do with
some pics to drive the message home a little
bit, but instead of that, this is excellent blog. A great read.
I will definitely be back.
Thanks for sharing such a fastidious opinion, paragraph
is fastidious, thats why i have read it entirely
Howdy, i read your blog from time to time and i own a similar one
and i was just wondering if you get a lot of spam responses?
If so how do you prevent it, any plugin or anything you can advise?
I get so much lately it’s driving me mad so any help is very much appreciated.
Excellent beat ! I would like to apprentice whilst you amend your site, how can i subscribe for
a weblog site? The account aided me a applicable deal.
I have been a little bit acquainted of this your broadcast offered shiny transparent idea
I am regular reader, how are you everybody? This paragraph posted at
this web page is truly fastidious.
Hi, I do believe this is an excellent website. I stumbledupon it 😉 I
am going to revisit once again since i have saved as a favorite it.
Money and freedom is the best way to change, may you be rich and continue
to help other people.
Hello there! This post couldn’t be written any better!
Reading through this post reminds me of my old room
mate! He always kept chatting about this. I will forward this
write-up to him. Pretty sure he will have a good read.
Thanks for sharing!
I am curious to find out what blog system you’re using?
I’m having some minor security issues with my latest site
and I’d like to find something more safe. Do you have any solutions?
I’m really loving the theme/design of your blog.
Do you ever run into any web browser compatibility issues?
A few of my blog readers have complained about my site not working correctly in Explorer but
looks great in Opera. Do you have any solutions to help fix this problem?
whoah this weblog is great i love studying your posts.
Stay up the good work! You know, lots of individuals are hunting round for this information, you could help
them greatly.
I have read so many content on the topic of
the blogger lovers but this piece of writing is actually a
fastidious paragraph, keep it up.
Hey would you mind sharing which blog platform you’re using?
I’m planning to start my own blog in the near future but I’m having a tough time selecting between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your design seems different then most blogs and I’m looking for something unique.
P.S Apologies for getting off-topic but I had to ask!
I do not even know the way I ended up here, however I believed this post was once good.
I do not recognise who you are but definitely you are going to a well-known blogger should you aren’t already.
Cheers!
That is a very good tip particularly to those fresh to the blogosphere.
Simple but very accurate information… Many thanks for sharing this one.
A must read post!
Right now it looks like Expression Engine is the preferred blogging
platform available right now. (from what I’ve read)
Is that what you are using on your blog?
Hello, i think that i saw you visited my site thus i came to “return the favor”.I’m trying to find things to improve my website!I suppose its ok to use a few of your ideas!!
Thanks to my father who stated to me regarding this webpage, this webpage is actually remarkable.
Hurrah! At last I got a web site from where I know
how to really obtain useful facts concerning my study and knowledge.
Greetings! I know this is kind of off topic but I was wondering if you knew where I could get a captcha
plugin for my comment form? I’m using the same blog platform as
yours and I’m having trouble finding one? Thanks a lot!
Hey there! I know this is kind of off topic but I was wondering which blog platform are you
using for this website? I’m getting fed up of WordPress because I’ve
had problems with hackers and I’m looking at options for
another platform. I would be fantastic if you could point me in the direction of a good platform.
Just want to say your article is as surprising. The clarity in your post is
simply excellent and i can assume you’re an expert on this
subject. Well with your permission allow me to grab your RSS
feed to keep up to date with forthcoming post. Thanks
a million and please continue the enjoyable work.
Hi, yup this piece of writing is genuinely fastidious and I have learned lot of things from
it on the topic of blogging. thanks.
I have to thank you for the efforts you have put
in penning this blog. I really hope to view the same high-grade content by you later on as well.
In fact, your creative writing abilities has encouraged me
to get my own site now 😉
Appreciate this post. Will try it out.
I’m really enjoying the theme/design of your web site.
Do you ever run into any browser compatibility problems?
A handful of my blog audience have complained about my website
not working correctly in Explorer but looks great in Chrome.
Do you have any suggestions to help fix this issue?
This text is invaluable. Where can I find out more?
Do you mind if I quote a few of your posts as long as I provide credit and sources back to your site?
My website is in the exact same niche as yours and my
users would really benefit from some of the information you provide here.
Please let me know if this okay with you. Many thanks!
For the reason that the admin of this web site is working,
no question very rapidly it will be renowned,
due to its feature contents.
If you are going for best contents like myself,
only go to see this site everyday as it provides quality
contents, thanks
What i don’t understood is if truth be told how you’re now not actually a lot more smartly-favored than you might be now.
You are very intelligent. You know thus significantly in relation to this matter, made me
individually believe it from numerous numerous
angles. Its like women and men aren’t involved except it’s one
thing to do with Girl gaga! Your own stuffs excellent. At all
times take care of it up!
Pretty! This was a really wonderful post. Thank you for supplying
this information.
Thanks for sharing such a good thinking, post is fastidious,
thats why i have read it fully
Hurrah, that’s what I was searching for, what a information! present here
at this web site, thanks admin of this web page.
Those are yours alright! . We at least need to get these people stealing images to start blogging! They probably just did a image search and grabbed them. They look good though!
I’m gone to inform my little brother, that he should also
pay a visit this website on regular basis to get updated
from hottest news update.
This post will help the internet visitors for creating new blog or even a blog from start to end.
Hello There. I found your blog the use of msn. This is a really smartly written article.
I’ll be sure to bookmark it and come back to learn more of your helpful information. Thank you for the post.
I will definitely comeback.
Hi to every one, it’s actually a fastidious
for me to go to see this site, it consists
of important Information.
I constantly emailed this web site post page to
all my associates, since if like to read it after that my contacts
will too.
Hey! Someone in my Facebook group shared this site with
us so I came to take a look. I’m definitely loving the information. I’m bookmarking and will be tweeting this to
my followers! Exceptional blog and excellent design and style.
What you published was actually very reasonable.
However, think about this, what if you were to write a awesome post title?
I am not suggesting your information isn’t good., however what if you added something to maybe grab folk’s attention? I mean 【BZOJ 4785】[ZJOI 2017] 树状数组 – Qizy's Database is kinda vanilla.
You should peek at Yahoo’s home page and watch how
they create article headlines to get viewers to click.
You might add a related video or a picture or two to get readers interested about everything’ve written.
Just my opinion, it would make your posts a little livelier.
I like what you guys tend to be up too. Such clever work
and reporting! Keep up the amazing works guys I’ve included you guys to my own blogroll.
Admiring the dedication you put into your site and detailed
information you provide. It’s awesome to come across a blog
every once in a while that isn’t the same old rehashed material.
Fantastic read! I’ve bookmarked your site and I’m adding your RSS feeds to my Google account.
Hi fantastic blog! Does running a blog like
this take a massive amount work? I’ve no understanding of programming but
I had been hoping to start my own blog in the near future.
Anyhow, if you have any ideas or techniques for
new blog owners please share. I know this is off topic but
I simply wanted to ask. Kudos!
Thanks for sharing your thoughts. I truly appreciate your efforts and I am waiting for your further
post thanks once again.
Excellent blog here! Also your website loads up very fast!
What host are you using? Can I get your affiliate
link to your host? I wish my site loaded up as quickly as yours lol
Undeniably believe that which you said. Your favorite
reason seemed to be on the internet the easiest thing
to be aware of. I say to you, I definitely get irked while
people think about worries that they just don’t know about.
You managed to hit the nail upon the top as well as defined out the whole thing without having side effect , people
could take a signal. Will likely be back to get more.
Thanks
Wow! After all I got a blog from where I be able to
actually take helpful data regarding my study and knowledge.
Hi, i think that i saw you visited my site so i came to go back the favor?.I am attempting to in finding things to improve my website!I guess its adequate to make use
of some of your ideas!!
This is a topic that’s close to my heart… Thank you! Exactly where are your contact details though?
Just wanna remark on few general things, The website design and style is perfect, the written content is real great : D.